package com.lucifer.sort;

/**
 * 归并排序
 *
 * @author yuxiao05@meituan.com
 * @create 2016-07-05 下午3:53
 */

public class MergeSort {

  private static final int INSERTIONSORT_THRESHOLD = 3;


  public static void main(String[] args){
    int[] a = new int[]{2,1,4,5,3,2,6};

    mergeSort(a, 0, a.length - 1);

    for (int i : a) {
      System.out.println(i);
    }
  }

  public static void mergeSort(int[] src, int left, int right) {
    int length = right - left;
    if (length < INSERTIONSORT_THRESHOLD) {
      insertSort(src);
      return;
    }
    int mid = (left + right) >>> 1;
    mergeSort(src, left, mid);
    mergeSort(src, mid, right);

    if (((Comparable) src[mid - 1]).compareTo(src[mid]) <= 0) {
      System.arraycopy(src, left, src, left, length);
      return;
    }

    int[] dest = new int[length];

    for (int i = 0,p = left, q = mid; i < right; i++) {
      if(p < mid && ((Comparable)src[p]).compareTo(src[q]) <= 0)
        dest[i] = src[p++];
      else
        dest[i] = src[q++];
    }

    src = dest;
  }

  public static void insertSort(int[] a){
    for (int i = 0, j = i; i < a.length -1; j = ++i) {
      int ai = a[i + 1];
      while (ai < a[j]) {
        a[j + 1] = a[j];
        if (j-- == 0)
          break;
      }
      a[j + 1] = ai;
    }
  }
}
